Performance evaluation and diagnosis is an important aspect of network management for all kinds of network. It is desirable to be able to monitor and asses parameters indicative of network performance for all components of a network in order to evaluate overall network performance, identify potential for performance improvement and diagnose problems. Particularly in the case of large scale communication networks, which may be substantially unregulated and highly heterogeneous, a single network operator or provider may not have control over all segments of a network that impact upon relevant performance data for that operator or provider. Certain segments of the network may therefore be unobservable, as the cooperation of network elements within those segments cannot be obtained.
Network Tomography has emerged as a promising technique enabling unobservable network performance parameters to be inferred without requiring cooperation of internal network components. Unobservable parameters are inferred solely on the basis of end-to-end (E2E) measurements conducted using edge nodes. Referring to the network 2 illustrated in FIG. 1, a series of probing paths is defined through the network, the probing paths originating and terminating with edge nodes 4 and traversing internal nodes 6. E2E measurements on data packets transmitted on the probing paths may be conducted with the cooperation of edge nodes 4. With an appropriately chosen set of probing paths, these E2E measurements may be used to infer node parameters for the internal network nodes 6. The task of finding the probing paths required to enable inferring of parameters for internal network nodes is referred to as the identifiability problem. The solution to this problem is a set of probing paths that provide full monitoring coverage of the network, that is that enable performance parameters for all internal network nodes to be inferred.
In practice, a majority of real networks are unidentifiable; structural limitations of their network topologies mean the identifiability problem cannot be solved. In such cases it is not possible to define a complete set of independent probing paths in the network which provides full monitoring coverage of the network, allowing a unique set of values for the parameters of interest to be inferred. Network Tomography techniques are therefore inapplicable to a majority of real networks. Considering an example network, identification methods can define a set of independent paths which is given by the cyclomatic complexity of the network graph:nPaths=Edges−Nodes+p_components+1
where nPaths represents the number of independent paths, Edges and Nodes represent the number of edges (links) and nodes of the network graph, and p_components represents the number of monitoring points, that is the edge nodes at which probing paths may originate or terminate. The unknown parameter values are equal in number to the Edges. In order to achieve full monitoring coverage of the network, the number of monitoring points must therefore be equal to Nodes−1. Such a large number of monitoring points is clearly impractical, as monitoring probes would be required on practically every node, whereas the purpose of Network Tomography is to obtain a picture of internal network functioning from the network periphery, i.e. having access to only a subset of nodes at the edge of the network.
In order to address the identifiability problem for complex real networks, additional constraints may be manually identified and applied to a network, so enabling full monitoring coverage with a reduced set of probing paths. However, a suitable set of additional constraints can be only achieved in certain specific cases, for example where the parameters to be inferred represent on/off processes such as loss measurements, where a packet can be lost or not lost. In all other cases, a unique solution cannot be found for the internal parameters. In a further complication for situations where additional constraints can be applied to a network, such additional constraints can only be defined according to the available monitoring points and so, depending on the network topology, they may not be sufficient to achieve full monitoring coverage of the network.